In Ethernet network architectures devices connected to the network compete for the ability to use the shared telecommunications path at any given time. Where multiple bridges or nodes are used to interconnect network segments, multiple potential paths to the same destination will exist in a meshed network architecture. The benefit of this architecture is that it provides path redundancy between bridges and permits capacity to be added to the network in the form of additional links. However the Ethernet paradigm of flooding and learning means that typically the breadth of connectivity that exists in a mesh network cannot be exploited at any given instant in time due to the requirement to ensure that no replicating path can loop. It should be noted that bridges can be interconnected by simple links or by shared LAN segments or by shared Virtual LAN segments. From the point of view of this document, segment, virtual segment and link are effectively interchangeable.
Each bridge node in an Ethernet network learns which devices or station can be reached via which local Ethernet segment by observing which segment packets from a given device arrive upon. When sending to an unknown device (one for which no forwarding information exists in the forwarding information base (FIB)), a bridge will replicate the message on all attached segments (this is known as flooding). This has two effects, bridges observing the flooded packet learn reachability information to the originating device, and there is an expectation that at some point in the future a reply solicited by the message or a subsequent unsolicited message from the intended destination device will be observed from which it can be noted via which segment the device replied to the message. Gradually, the bridge builds a picture for itself of what next segment is appropriate to reach specific devices in the network. When subsequent messages are sent, the bridge can use its FIB to determine which locally attached segment to forward it to. The approach of allowing the bridges to learn the network through experience is known as transparent bridging. One key benefit of the technique is that bridging does not require setup by an administrator.
In a mesh, when a packet is forwarded between peer devices it may be possible for the packet to traverse through multiple bridges via a plurality of paths. However, if the packet were to be sent on multiple routes simultaneously, network congestion would increase and possible looping conditions may result. This scenario arises in a mesh for multicast and/or flooded traffic as the number of copies of a given packet would grow exponentially if unchecked. A Spanning Tree Protocol (STP) algorithm is utilized to eliminate packet duplication by iteratively electing a spanning tree logically connecting the set of participating nodes. The algorithm is specifically constructed to avoid bridge loops (multiple paths linking one segment to another, resulting in an infinite loop situation) The algorithm typically computes the shortest path from all segments to an elected root bridge. If the best path fails, the algorithm recalculates the network and finds the next best route. If the root fails, a new root is elected and the algorithm re-runs. At the same time, all learned MAC information with respect to device reachability is discarded, and the FIBs are gradually repopulated via flooding and learning once the new spanning tree is established.
STP provides connectivity while preventing undesirable loops in a network that would exist if there were multiple active paths between nodes or devices. If loops were permitted to form, packets entering the loop circulate until a node takes action to remove the packet or the loop is broken. If the bridges in the loop flood, or the packet is a multicast packet, additional copies of the packet will be generated in each traversal of the loop, a highly undesirable outcome. To establish loop free connectivity, STP creates a tree that spans all of the bridges in an extended network, forcing redundant paths into a standby, or blocked, state. STP allows only one active path at a time between any two points in the network, this prevents loops but the additional capacity associated with physical mesh connectivity is not utilized. STP was designed for nodes without state memory for bridge simplicity. However the simplistic approach to loop-free connectivity can result in an excess of un-used network capacity due to the requirement to prune the physical topology to a single loop-free spanning tree.
Root election during STP convergence is determined by the set of bridges determining which bridge has lowest ID and then each bridge determining the next hop on the path of lowest cost to the bridge with the lowest ID, or “root”. The bridges initially advertise their own ID and null cost in spanning tree protocol exchanges. When they receive an advertisement with a lower ID, they stop advertising their own ID and advertise the lower ID and cost. Similarly when they see a segment with a lower cost to the current lowest ID, they modify both their re-radiated advertisements and internal state accordingly. Eventually the network will converge on a common view of the lowest ID, and each bridge knowing the next segment on the lowest cost path to the root. If costs change, or if one network segment in the spanning tree becomes unreachable, the STP algorithm iteratively computes a new spanning tree topology to offer connectivity utilizing the revised set of segments. While the bridges of the network are not converged, ports are blocked stopping network traffic in order to prevent looping and replication.
FIG. 1 shows an example of how a spanning tree protocol algorithm in a mesh network affects the forwarding of a packet through the network. From a source device A, the STP algorithm has mapped out a path from through the network by determining links between each node that achieve the lowest cost (shown as multicast route). This route determines the paths available for all the traffic traversing the network. Device A, attached to bridge 110 sends a packet to device B which is new on the network. The bridges of the network do not have forwarding tables populated for this device. The packet is flooded into the network to each bridge node by the path defined by the spanning tree. Following the spanning tree packets are forwarded from bridge 110 through bridge 112. The links from bridge 110 to the neighboring bridges 116 and 120 are not utilized as they have been disabled or blocked and are not part of the spanning tree. From bridge 112 the packet is forwarded to the other nodes of the network, bridges 120, 122, 124, and 114. Bridge 114 in turn forwards the packet to bridges 116 and 118. Device B receives a flooded copy of the packet via bridge 122. All intermediate bridges will note the segment of arrival for source “A” and update their FIBs accordingly. A response sent by device B will then traverse the network directly to device A without being flooded as the return route is known to the intermediate bridges in the network. Essentially a flood of packets enters the network with one response back from device B to device A, and similar to how intermediate bridges learned optimal forwarding to “A” observing the initial message, they learn optimal forwarding to “B” observing the response.
Using STP in an Ethernet network limits the utilization efficiency of thee links or LAN segments in the network. Segments and links not selected by the STP algorithm are disabled and essentially not part of the active network topology until some change in the physical topology of the network occurs such that the link is part of the resultant spanning tree. This strands the capacity of these links. In a small LAN environment this may not be an issue, however in a WAN or provider network unused capacity both impacts scaling and represents under utilized investment. In addition when a failure does occur, the performance of the whole network is impacted during the time required to re-converge STP and stabilize all the bridges in the network. The path taken by a given packet utilizing spanning tree is typically not the shortest path between the source and destination as the root of the current spanning tree is not necessarily on the physical shortest path. For example, if device C were connected to neighboring bridge 116, packets from device A would still have to traverse bridges 112 and 114 based upon the current spanning tree which does not necessarily provide the shortest path to bridge 116. Finally in a provider network there may be many small communities of interest in the form of virtual private networks, and to constrain flooding of information within those communities of interest requires typically a distinct spanning tree per community.
Various methods have been proposed to improve STP performance and mitigate loop formation in meshed Ethernet network. Some current proposals require an MPLS-like label or the additional of time-to-live (TTL) field to Ethernet packet to limit the impact of looping. However fundamental data plane modifications are required to implement these solutions which limits their utility. In addition, only limiting the number of times a packet may replicate is a demonstrably incomplete solution to the looping problem.
In order to scale Ethernet from the LAN space to the WAN or provider network space an improved mechanism for creating efficient loop-free Ethernets is required. This is one which makes superior utilization of mesh connectivity, constrains the impact of failures or topology changes (e.g. does not interrupt or minimizes interruptions of connectivity), and suppresses loops or mitigates the effect of looping. Therefore, there is a need for an Ethernet network with improved network utilization while avoiding the pitfalls of transient or persistent Loops.